package com.suanfa.collect;

/**
 * 单调递增的数组被旋转过，求目标下标，时间复杂度 O(logn)
 */
public class BinSearch2 {

    public static void main(String[] args) {
        int[] arr = new int[]{4,5,6,7,0,1,2};
        int target =3;
        System.out.println(getResult(arr, target));

    }


    public static int getResult(int[] arr, int target){
       if(arr.length == 0){
           return -1;
       }
       int start = arr[0], end = arr[arr.length-1];

       //从结尾开始遍历
       if(target <= end){
           int index = arr.length-1;
           int pre = Integer.MAX_VALUE;
           while (index > -1){
               if(arr[index] == target){
                   return index;
               }
               if(arr[index] > pre){
                   return -1;
               }
               pre = arr[index];
               index -- ;
           }
       }
       //从开头开始遍历
        if(target >= start){
            int index = 0;
            int pre = Integer.MIN_VALUE;
            while(index < arr.length){
                if(arr[index] == target){
                    return index;
                }
                if(arr[index] < pre){
                    return  -1;
                }
                pre = arr[index];
                index ++;
            }
        }
       return  -1;
    }

}
